package main

func buildGraph(prerequisites [][]int) map[int][]int {
	graph := make(map[int][]int)
	for _, pair := range prerequisites {
		graph[pair[1]] = append(graph[pair[1]], pair[0])
	}
	return graph
}

var visited []bool
var onPath []bool

// return has cycled
func traverse(graph map[int][]int, beg int) bool {
	if onPath[beg] {
		return true
	}
	if visited[beg] {
		return false
	}
	visited[beg] = true
	onPath[beg] = true
	for _, next := range graph[beg] {
		if traverse(graph, next) {
			return true
		}
	}
	onPath[beg] = false
	return false
}

func canFinish(numCourses int, prerequisites [][]int) bool {
	visited = make([]bool, numCourses)
	onPath = make([]bool, numCourses)
	graph := buildGraph(prerequisites)
	for i := 0; i < numCourses; i++ {
		if traverse(graph, i) {
			return false
		}
	}
	return true
}

func main() {

}
